package io.github.hadyang.leetcode.tencent;

import org.junit.Test;

/**
 * 最长回文子串
 *
 * <p>给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * <p>示例 1：
 *
 * <p>输入: "babad"
 *
 * <p>输出: "bab"
 *
 * <p>注意: "aba" 也是一个有效答案。
 *
 * <p>示例 2：
 *
 * <p>输入: "cbbd" 输出: "bb"
 */
public class String896 {

  @Test
  public void test() {
    //        System.out.println(longestPalindrome("babad"));
    //        System.out.println(longestPalindrome("cbbd"));
    //        System.out.println(longestPalindrome("aaaa"));
    System.out.println(longestPalindrome("abcda"));
  }

  public String longestPalindrome(String s) {
    if (s.length() == 0) return "";

    boolean[][] t = new boolean[s.length()][s.length()];
    for (int i = 0; i < t.length; i++) {
      t[i][i] = true;
    }

    int maxi = 0, maxj = 0;
    for (int i = 0; i < t.length; i++) {
      for (int j = 0; j < i; j++) {
        if (i == j) continue;

        t[i][j] = s.charAt(i) == s.charAt(j) && (i - j < 2 || t[i + 1][j - 1]);
        if (t[i][j] && Math.abs(maxj - maxi) < Math.abs(j - i)) {
          if (i < j) {
            maxi = i;
            maxj = j;
          } else {
            maxi = j;
            maxj = i;
          }
        }
      }
    }

    return s.substring(maxi, maxj + 1);
  }
}
